package 题目集.树.树链剖分;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * 如果两个点在同一条重链上，那么较高点就是lca
 * 如果不在，则向上跳到同一条重链上，然后再比较。
 *  倍增lca，是通过每个节点维护log(n)个2^i长度的块信息，每个块维护祖先节点信息，通过跨越块来求lca。每个块也可以维护其他信息。
 *  树剖lca，是通过将树划分为多条树干，其中越接近根的树干越粗（长度越大），让两个节点每次跳向更粗的树干，最后到达同一树干上，最后这个树干上的较高点就是lca。
 *  树剖lca并没有维护块信息，但树剖可以通过排列这些树干，使得树变成一个线性结构，从而可以通过其他数据结构（线段树）维护块信息。
 */
public class ch02_重链剖分求lca {
    static int maxn = 500010;
    static List<Integer>[] graph;
    static int n, m, r;
    static int[] deep = new int[maxn];
    static int[] p = new int[maxn];
    static int[] size = new int[maxn];
    static int[] son = new int[maxn];
    static int[] top = new int[maxn];

    public static void main(String[] args) {
        Reader2 sc = new Reader2(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        r = sc.nextInt();
        graph = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        buildSize(r, 0);
        buildChain(r, r);
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            Reader2.pw.println(lca(u, v));
        }
        Reader2.pw.flush();
    }

    public static int lca(int high, int low) {
        while (top[high] != top[low]) {
            if (deep[top[high]] > deep[top[low]]) {
                low = high ^ low;
                high = high ^ low;
                low = high ^ low;
            }
            low = p[top[low]];
        }
        return deep[high] < deep[low] ? high : low;
    }

    private static void buildChain(int u, int t) {
        top[u] = t;
        if (size[u] > 1) {
            buildChain(son[u], t);
            for (Integer v : graph[u]) {
                if (v != p[u] && v != son[u]) {
                    buildChain(v, v);
                }
            }
        }
    }

    public static void buildSize(int u, int fa) {
        deep[u] = deep[fa] + 1;
        p[u] = fa;
        size[u] = 1;
        for (Integer v : graph[u]) {
            if (v != fa) {
                buildSize(v, u);
                if (size[son[u]] < size[v]) {
                    son[u] = v;
                }
                size[u] += size[v];
            }
        }
    }

    static class Reader2 {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        public Reader2(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }
}
